A hypergraph is a generalization of a graph in which an edge can connect any number of vertices. Formally, a hypergraph G=(V, E) is defined as a set of vertices (or nodes) V and a set of hyperedges (or edges) E, where each hyperedge is a subset of the vertex set V, and the size (or order) of a hyperedge is the cardinality of this subset.
Hypergraph partitioning is an important problem with extensive application to many areas, including VLSI design, efficient storage of large databases on disks, and data mining. The k-way partitioning problem assigns each node of a hypergraph into one of k bins while attempting to minimize the “cut metric”, i.e., the number of hyperedges that connect nodes assigned to multiple bins. Real world partitioning problems often have multi-valued cost functions in addition to the edge-cost and obey various constraints. For an application that partitions integrated circuit designs, the hypergraph is a netlist that represents a design that needs to be partitioned into k field-programmable gate array (FPGA) units of a system for FPGA-based prototyping. In addition to the cut metric, the application requires attention to the timing of the system and to the number and configuration of the wires available to interconnect the FPGA units.
The most common method used for partitioning is the multi-level partitioning approach developed by Karypis and Kumar for the hMETIS system. This approach begins by coarsening the hypergraph using connectivity-based clustering and then repeatedly applying the Fiduccia-Mattheyses (FM) algorithm to partition the hypergraph followed by “un-coarsening” the graph.
The quality of results (QoR) of hMETIS approach is sensitive to the quality of the clustering and to the quality of the initial solution at the coarsest level of the hypergraph. The FM algorithm can get stuck at local minima set up in the first partitioning step. Also, k-way FM algorithm's runtime complexity is linear in k. The common use of recursive bi-partitioning to reduce the complexity to log(k) is impractical given the global nature of the non-cut metrics in this problem.